﻿using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;

namespace Acoris.Foundation
{
    class RopeNode
    {
        internal readonly RopeNode EmptyNode = new RopeNode{};
        internal const int MaxSize = 256;

        internal char[] contents;
        internal int length;
        internal byte height;
        internal RopeNode left;
        internal RopeNode right;
        internal volatile bool share;

        internal int Balance {
            get {
                return left.height - right.height;
            }
        }

        #region Clone / CloneIfShare / Lock

        internal RopeNode Clone()
        {
            // clone a new node from it
            var contents = new char[MaxSize];
            this.contents.CopyTo(contents, 0);
            return new RopeNode
            {
                contents = contents,
                height = this.height,
                left = this.left,
                right = this.right,
                length = this.length,
                share = this.share
            };
        }

        internal RopeNode CloneIfShare()
        {
            // if this is a shared node we clone it
            // else return itself

            // 共享节点一般在Merge操作之后出现，这时候的空节点并不会变成null
            // 而是换作Empty Node这个节点引用。为了避免一系列InvaliableOperation
            // 我们需要一个Lock方法让这些共享节点变成不再可以共享            
            if (share) {
                return Clone();
            }
            return this;
        }

        internal void Lock()
        {
            if (share) {
                this.share = true;

                if (left != null) {
                    left.Lock();
                }

                if (right != null) {
                    right.Lock();
                }
            }
        }

        #endregion

        #region SplitAfter / Concat / Insert

        internal static RopeNode Concat(RopeNode left, RopeNode right)
        {
            if (left == null) {
                return right;
            }

            if (right == null) {
                return left;
            }

            if (left.length + right.length <= MaxSize) {
                left = left.CloneIfShare();
                CopyNode(right, left.contents, left.length);
                left.length += right.length;
                return left;
            }
            else {
                var node = new RopeNode
                {
                    left = left,
                    right = right,
                    height = (byte)(1 + Math.Max(left.height,right.height)),
                    share = false,
                    length = left.length + right.length
                };
                node.Rebalance();
                return node;
            }
        }

        internal RopeNode Insert(int offset, RopeNode node)
        {
            var newPart = new RopeNode();
            var left = Clone();
            var right = Concat(left.Split(offset),node);
            left.length = offset;

            newPart.length = left.length + right.length;
            newPart.height = (byte)(1 + Math.Max(left.height, right.height));
            newPart.share = false;
            newPart.left = left;
            newPart.right = right;            
            return newPart;
        }

        internal static RopeNode IndexOf(int offset,RopeNode node)
        {
            Debug.Assert(offset < node.length);
            if(node.height == 0 && offset < node.length) {
                return node;
            }
            else if(offset > node.left.length && node.right.length > offset) {
                return IndexOf(offset - node.left.length, node.right);
            }
            else {
                throw new Exception();
            }
        }

        internal RopeNode Split(int offset)
        {
            Debug.Assert(!share && height == 0 && contents != null);
            if(offset == 0) {
                return CloneIfShare();
            }

            if(offset == this.length) {
                return null;
            }

            var newContents = new char[MaxSize];
            var length = this.length - offset;
            Array.Copy(contents, offset, newContents, 0, length);
            return new RopeNode
            {
                length = length,
                contents = newContents,
                height = 0,
                share = false
            };
        }

        #endregion

        #region Replace / RemoveRange

        internal static RopeNode Replace(RopeNode node, int offset, int count)
        {
            return null;
        }

        internal static RopeNode RemoveRange(int offset, int count)
        {
            return null;
        }

        #endregion

        #region Rebalance / RotateToLeft / RotateToRight

        internal void Rebalance()
        {
            while(Math.Abs(Balance) > 1) {

            }
        }

        internal void Merge()
        {
            this.height = 0;
            if (length <= MaxSize) {
                if (share) {
                    contents = new char[MaxSize];
                    Array.Copy(left.contents, contents, left.length);
                }
                else {
                    contents = left.contents;
                }                
                CopyNode(right, contents, length);
                this.length = left.length + right.length;
                this.left = null;
                this.right = null;
                Lock();
            }
        }

        internal void RotateToRight()
        {
            /* 
			 * 
			 *       node            node
			 *       /  \            /  \
			 *     left  C   ->    A  right
			 *     / \                 /  \
			 *    A   B               B    C
			 */

            var right = this.left;
            var a = this.left.left;
            var b = this.left.right;
            var c = this.right;

            right.left = b;
            right.right = c;
            right.length = b.length + c.length;
            right.height = (byte)(1 + Math.Max(b.height, c.height));
            right.share = false;

            this.left = a;
            this.right = right;
            this.length = a.length + right.length;
            this.height = (byte)(1 + Math.Max(this.left.height, this.right.height));
            this.share = false;

            right.Merge();
        }

        internal void RotateToLeft()
        {
            /*
			 * 
			 *       node             node
			 *       /  \             /  \
			 *      A   right   ->  left  C
			 *           / \        / \
			 *          B   C      A   B
			 */
            var left = this.right;
            var a = this.left;
            var b = this.right.left;
            var c = this.right.right;

            left.left = a;
            left.right = b;
            left.length = a.length + b.length;
            left.height = (byte)(1 + Math.Max(a.height, b.height));
            left.share = false;

            this.left = left;
            this.right = c;
            this.length = left.length + c.length;
            this.height = (byte)(1 + Math.Max(left.height, c.height));
            this.share = false;

            left.Merge();
        }

        #endregion

        #region CreateFromArray / CreateFromString / SetContent / CopyNode

        internal static RopeNode CreateFromArray(char[] array,int index,int count)
        {
            var totalLength = count;
            var leafNode = (totalLength + MaxSize - 1) / MaxSize;
            var node = CreateNode(leafNode,totalLength);
            node.SetContent(0, array, index, totalLength);
            node.Rebalance();
            return node;
        }

        internal static RopeNode CreateFromString(string text)
        {
            var array = text.ToCharArray();
            return CreateFromArray(array,0,array.Length);
        }

        static RopeNode CreateNode(int leafNode, int totalLength)
        {
            var node = (RopeNode)null;
            if (leafNode == 1) {
                node = new RopeNode
                {
                    length = totalLength,
                    height = 0,
                    contents = new char[MaxSize],
                    share = false
                };
                return node;
            }
            else {
                var leftLeafNode = leafNode / 2;
                var leftLength = leftLeafNode * MaxSize;
                var rightLeafNode = leafNode - leftLeafNode;

                var left = CreateNode(leftLeafNode,leftLeafNode * MaxSize);
                var right = CreateNode(rightLeafNode,rightLeafNode * MaxSize);
                node = new RopeNode
                {
                    left = left,
                    right = right,
                    height = (byte)(Math.Max(left.height, right.height) + 1),
                    share = false
                };
            }

            return node;
        }

        internal void SetContent(int index, char[] array, int arrayIndex, int count)
        {
            if (height == 0) {
                Debug.Assert(length >= count);
                Debug.Assert(index > -1);
                Array.Copy(array, arrayIndex, contents, index, count);
            }
            else {
                if (index + count <= left.length) {
                    this.left.SetContent(index, array, arrayIndex, count);
                }
                else if (index + count >left.length) {
                    this.right.SetContent(index - left.length, array, arrayIndex, count);

                }
                else {
                    var rightIndex = left.length - index;
                    left.SetContent(index, array, arrayIndex, left.length);
                    if (right != null) {
                        right.SetContent(0, array, arrayIndex + rightIndex, count - rightIndex);
                    }
                }
            }
        }

        internal static void CopyNode(RopeNode node,char[] array,int arrayIndex)
        {
            if (array.Length < node.length && arrayIndex + node.length <= array.Length) {
                throw new IndexOutOfRangeException();
            }
            Array.Copy(node.contents, 0, array, arrayIndex, node.length);
        }

        #endregion        

        public override string ToString()
        {
            if (height == 0) {
                return $"length:{length}";
            }
            else {
                return $"height:{height}";
            }
        }
    }
}
